/**
 * 归并排序
 */

// 递归方式
Array.prototype.mergerRecursion = function(){
   
     function merger(arr ,start, end){
           if(start == end) return 
           let midIndex = Math.floor((start+end)*0.5);
           let leftStart = start;
           let leftEnd = midIndex;
           let rightStart =  midIndex+1;
           let rightEnd = end;

           let leftPointer = leftStart;             // 左子数组指针
           let rightPointer = rightStart         // 右子数组指针
      
          merger(arr, leftStart , leftEnd );
          merger(arr, rightStart, rightEnd);

          let temp = [];
          
          while(leftPointer <= leftEnd && rightPointer <= rightEnd){
                if(arr[leftPointer] < arr[rightPointer]){               // 将左表元素加入临时数据
                      temp.push(arr[leftPointer])     
                      leftPointer++            
                }else{
                    temp.push(arr[rightPointer])                          // 将右表元素加入临时数据
                    rightPointer++  
                }    
           }
         
           // 将左表剩余元素加入临时表
           while(leftPointer <= leftEnd){
                temp.push(arr[leftPointer])     
                leftPointer++   
           }
           // 将右表剩余元素加入临时表
           while(rightPointer <= rightEnd){
                temp.push(arr[rightPointer])                          
                rightPointer++  
           }
           //  将排序好的元素重新赋值给数组
           for(let i = 0 ; i <temp.length; i++){
                arr[start+i] = temp[i]
           }
           return arr
     }

     return merger(this,0, this.length-1)
}

// 循环方式(个人认为比递归好理解)
Array.prototype.mergerCirculation = function(){
      let k = 1
      while(k < this.length ){
          let IntervalNumber  = Math.floor(this.length/k); // 区间个数
          for (let i = 0; i< IntervalNumber; i+=2) {
             let leftStart = i * k ;
             let leftEnd = i * k  + k -1
             let rightStart =  (i + 1) * k
             let rightEnd =  (i + 1) * k + k -1 >= this.length - 1 ?  this.length - 1 : (i + 1) * k + k -1 ;

             let leftPointer =  leftStart;
             let rightPointer =  rightStart;
             let temp = [];
             // 归并核心 将两个数组中小的元素放在前面
             while(leftPointer <= leftEnd && rightPointer <= rightEnd){
                  if(this[leftPointer] < this[rightPointer]){
                      temp.push(this[leftPointer]);
                      leftPointer++;
                  }else{
                    temp.push(this[rightPointer]);
                    rightPointer++;
                  }
             }
             while(leftPointer <= leftEnd){
               temp.push(this[leftPointer]);
               leftPointer++;
             }
             while(rightPointer <= rightEnd){
               temp.push(this[rightPointer]);
               rightPointer++;
             }
           
             for(let i = 0;i < temp.length ;i ++){
               this[leftStart +i] = temp[i]
             }
          }  
          k *= 2
      }
}

let a = [4,2,-1,5,1,100,-1000,1,10,100,11000];
a.mergerRecursion();
console.log(a);
